package offerbook.Code27_BST_Link_Array_Converse;

import utils.TreeNode;
import utils.TreeUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * @date 2020/3/10 13:41
 */
public class Code27_ConvertBSTtoLink {
    /**
     * 方式1：中序遍历到数组，然后把数组中串起来。需要额外数组O(n)
     * @param treeNode
     * @return
     */
    public TreeNode Convert1(TreeNode treeNode) {
        if(treeNode ==null) return treeNode;
        List<TreeNode> list = new ArrayList<>();
        inOrder(treeNode,list);
        return convert(list);
    }

    /**
     * 方式2：遍历的过程中传起来，除了递归不需要额外空间。
     * 注意：也可以使用迭代版本的中序遍历串起来。
     *
     */
    TreeNode pre;
    public TreeNode Convert2(TreeNode treeNode) {
        if (treeNode == null) return treeNode;
        inOrder(treeNode);
        //当前pre指向了中序遍历的最后一个节点，要再次翻转回来
        while (pre.left != null) pre = pre.left;
        //这里也可以在设定一个全局变量，引用第一个遍历的节点，避免再次反序遍历
        return pre;
    }

    private void inOrder(TreeNode treeNode) {
        if(treeNode == null) return;
        //中序遍历
        inOrder(treeNode.left);
        if(pre == null) {//第一个节点
           pre = treeNode;
           //the frist head = pre,可以再增加一个变量
        }else {
            treeNode.left = pre;
            pre.right = treeNode;
            pre = treeNode;
        }
        inOrder(treeNode.right);
    }

    /**
     * 方式3：反中序遍历。右 ->中 ->左，这样pre最后是左侧
     */
    public TreeNode Convert3(TreeNode treeNode) {
        if (treeNode == null) return treeNode;
        uninOrder(treeNode);
        //当前pre反中序遍历的最后一个节点，也就是中序遍历的第一个节点
        return pre;
    }

    private void uninOrder(TreeNode treeNode) {
        if(treeNode == null) return;
        //中序遍历
        uninOrder(treeNode.right);
        if(pre == null) {//第一个节点
            pre = treeNode;
        }else {
            treeNode.right = pre;
            pre.left = treeNode;
            pre = treeNode;
        }
        uninOrder(treeNode.left);
    }


    private TreeNode convert(List<TreeNode> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).right = list.get(i+1);
            list.get(i+1).left = list.get(i);
        }
        return list.get(0);
    }

    private void inOrder(TreeNode treeNode, List<TreeNode> list) {
        if(treeNode == null) return;
        inOrder(treeNode.left,list);
        list.add(treeNode);
        inOrder(treeNode.right,list);
    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        TreeUtil.printTree(treeNode);


    }
}
